// Created by WXX on 2021/11/24 10:08
#include <iostream>
#include <vector>
#include <unordered_map>

using namespace std;

/**
 * 执行用时：8 ms, 在所有 C++ 提交中击败了44.21%的用户
 * 内存消耗：9.9 MB, 在所有 C++ 提交中击败了5.02%的用户
 */
class Solution {
public:
    int largestSumAfterKNegations(vector<int>& nums, int k) {

        unordered_map<int, int> cnt;
        int t = 1e8;
        for (int x : nums) {
            cnt[x]++;
            t = min(t, abs(x));
        }

        for (int i = -100; i < 0 && k > 0; i++) {
            while (cnt[i] > 0 && k > 0) {
                cnt[i]--;
                cnt[-i]++;
                k--;
            }
        }

        int res = 0;
        for (int i = -100; i <= 100; i++) res += i * cnt[i];

        if (k % 2) res -= 2 * t;

        return res;
    }
};

int main() {

    vector<int> nums = {4, 2, 3};
    cout << Solution().largestSumAfterKNegations(nums, 1) << endl;  // 5

    return 0;
}
